package MST.prim;

import java.util.Arrays;

/**
 * 解决最小生成树
 * 修路问题 --- 普利姆（Prim）算法
 */
public class Prim {
    private static final int INF = Integer.MAX_VALUE;

    // 为了描述地点、路之间的关系需要一个图
    static class MGraph {
        int nums; // 表示图中节点的个数
        char[] data; // 存放节点的数据（名称）
        int[][] weight; // 邻接矩阵来存放各个节点之间的关系，以及权值

        public MGraph(int nums) {
            this.nums = nums;
            data = new char[nums];
            weight = new int[nums][nums];
        }
    }

    // 创建最小生成树
    static class MinTree {
        // 创建图的邻接矩阵
        /**
         *
         * @param mGraph 传入的图的对象
         * @param nums 节点个数
         * @param data 节点名称
         * @param weight 图的邻接矩阵
         */
        public void creatGraph(MGraph mGraph, int nums, char[] data, int[][] weight) {
            // 遍历节点
            int i, j;
            for (i = 0; i < nums; i++) {
                mGraph.data[i] = data[i];
                for (j = 0; j < nums; j++) {
                    mGraph.weight[i][j] = weight[i][j];
                }
            }
        }

        /**
         * 显示图的邻接矩阵
         * @param mGraph
         */
        public void showGraph(MGraph mGraph) {
            for (int[] edges : mGraph.weight) {
                System.out.println(Arrays.toString(edges));
            }
        }

        /**
         * 编写prim算法得到最小生成树
         * @param mGraph 图对象
         * @param n 从哪个节点开始 0...
         */
        public void prim(MGraph mGraph, int n) {
            // 使用一个数组来标记这个节点是否已经被访问过了
            int[] visited = new int[mGraph.nums];
            visited[n] = 1; // 别访问过了就标记为一
            for (int k = 1; k < mGraph.nums; k++) { // 寻找mGraph.nums - 1条边
                // 记录所以周围节点与已经访问过节点之间的最小权值的坐标
                int h1 = -1;
                int h2 = -1;
                int minWeight = INF;
                // 遍历图中的关系找到最小权值的节点
                for (int i = 0; i < mGraph.nums; i++) {
                    for (int j = 0; j < mGraph.nums; j++) {
                        // 一个节点是遍历过的且另一个与之相连的节点是未曾遍历过的，且他们边上的权值是当前最小的则更新
                        if (visited[i] == 1 && visited[j] == 0 && mGraph.weight[i][j] < minWeight) {
                            h1 = i;
                            h2 = j;
                            minWeight = mGraph.weight[i][j];
                        }
                    }
                }
                if (h2 == -1) {
                    return;
                }
                // 至此就找到了符合要求的那个节点
                System.out.println("边<" + mGraph.data[h1] + "," + mGraph.data[h2] + "> 权值为：" + minWeight);
                // 更新已经访问过的节点
                visited[h2] = 1;
            }
        }
    }

    public static void main(String[] args) {
        char[] data = new char[] {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int nums = data.length;
        int[][] weight = new int[][] {
                {INF, 5, 7, INF, INF, INF, 2},
                {5, INF, INF, 9, INF, INF, 3},
                {7, INF, INF, INF, 8, INF, INF},
                {INF, 9, INF, INF, INF, 4, INF},
                {INF, INF, 8, INF, INF, 5, 4},
                {INF, INF, INF, 4, 5, INF, 6},
                {2, 3, INF, INF, 4, 6, INF}
        };
        MGraph mGraph = new MGraph(7);
        MinTree minTree = new MinTree();
        minTree.creatGraph(mGraph, nums, data, weight);
        minTree.showGraph(mGraph);
        minTree.prim(mGraph, 0);
    }
}
